The invention relates to multicasting video.
Development of a high-speed internetworking infrastructure (e.g., the Internet) and digital video technology has led to the emergence of several networked multimedia applications that include streaming video as a media component. Such applications include streaming video broadcasts, distance learning, corporate telecasts, narrowcasts, etc. Digital video traffic typically exhibits high bandwidth requirements and significant burstiness at multiple time scales, owing to the encoding schemes and content variation between and within video scenes. For example, MPEG (Motion Pictures Experts Group) encodes a video in different size frames. Additionally, the information needed to encode each frame can vary, for example, based on how much video information changes from image to image. When combined with other media such as audio, text, HTML (HyperText Markup Language), and images, multi-media transmissions can become even burstier. The high bandwidth requirements coupled with the bursty variable-rate nature of these streams complicates the design of efficient storage, retrieval, and transport mechanisms for such media.
A technique known as workahead smoothing can yield significant reductions in peak rate and rate variability of video transmissions from a server to a single client (i.e. unicast). In smoothing, by transmitting frames early, the sender, or a smoothing node, can coordinate access with the client and can send large video frames at a slower rate without disrupting continuous playback at the client. The frames transmitted ahead of time are temporally stored in buffers present in the server and the client. A characteristic of the smoothed transmission schedule is that the smoothing benefit is a non-decreasing function of buffer sizes present.
For many applications, streaming video transmission occurs from a server simultaneously to a large number of heterogeneous clients that have different resource capacities (e.g. buffer sizes) and that are scattered geographically over a heterogeneous internetwork that has different resource capacities in different segments. Described herein are techniques that can reduce the bandwidth overhead for such simulcast services.
In general, in one aspect, the invention features a method of multicasting video to multiple client nodes via intermediate nodes. The method includes accessing video information descriptive of the video to be multicast, accessing information describing a distribution tree of nodes from a source of the video to the multiple clients nodes via one or more internetwork nodes, accessing rate constraints of nodes in the distribution tree, accessing buffer allocations of the nodes in the distribution tree, and determining one or more smoothed transmission schedules for each node in the distribution tree based on the accessed video information, the accessed information describing the distribution tree, the accessed rate constraints of nodes in the distribution tree, and the accessed buffer allocations of the nodes, the one or more transmission schedules describing the transmission of video data to one or more children nodes.
Embodiments may include one or more of the following features. Accessing buffer allocations can include determining buffer allocations based on the accessed video information, the accessed information descriptive of a distribution tree, and the accessed rate constraints. Accessing rate constraints may include receiving rate constraints. The determining may include determining an upper constraint for each node, determining a lower constraint for each node, and determining a smoothing schedule based on the determined upper and lower constraints. The determining of a smoothed schedule may use majorization. The method may further include distributing the determined transmission schedules to nodes in the distribution tree. The determined transmission schedules may include schedules that cause at least one node to differentially cache data for distribution to the at least one node""s children.
In general, in another aspect, the invention features a computer program product, disposed on a computer readable medium, for multicasting video to multiple client nodes via intermediate nodes. The program includes instructions for causing a processor to access video information descriptive of the video to be multicast, access information describing a distribution tree of nodes from a source of the video to the multiple clients nodes via one or more internetwork nodes, access rate constraints of nodes in the distribution tree, access buffer allocations of the nodes in the distribution tree, and determine one or more smoothed transmission schedules for each node in the distribution tree based on the accessed video information, the accessed information describing the distribution tree, the accessed rate constraints of nodes in the internetwork, the accessed buffer allocations of nodes in the internetwork, and the one or more transmission schedules describing the transmission of video data to one or more children nodes.
Unless otherwise defined, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. Although methods and materials similar or equivalent to those described herein can be used in the practice or testing of the present invention, suitable methods and materials are described below. All publications, patent applications, patents, and other references mentioned herein are incorporated by reference in their entirety. In case of conflict, the present specification, including definitions, will control.
In addition, the materials, methods, and examples are illustrative only and not intended to be limiting.